package leetcode; /**
 * description:
 * author:张腾
 * date:2021-07-03
 */

import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * 给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
 */
public class leetcode451 {
    class Node {
        char c;
        int v;
        Node(char _c, int _v) {
            c = _c; v = _v;
        }
    }
    public String frequencySort(String s) {
        char[] c = s.toCharArray();
        HashMap<Character, Integer> map = new HashMap<>();
        for (char cur : c) {
            map.put(cur,map.getOrDefault(cur,0)+1);
        }
        PriorityQueue<Node> queue = new PriorityQueue<>((a,b)->{
            if (a.v!=b.v) return b.v-a.v;
            return a.c-b.c;
        });
        for (Character c1 : map.keySet()) {
            queue.add(new Node(c1,map.get(c1)));
        }
        StringBuffer sb = new StringBuffer();
        while (!queue.isEmpty()){
            Node node = queue.poll();
            int k = node.v;
            while (k>0) sb.append(node.c);
        }
        return sb.toString();
    }
}
